package edu.cmu.km.kernel.string;

public class StringKernel {
	private String s, t;

	public int editDistance() {
		return 0;
	}

	public int alignmentDistance() {
		return 0;
	}

	/**
	 * The string edit distance defined as the minmal cost of operations that change x to y. 
	 * The cost of elementory eidt is considered to be 1. 
	 * This method should be symmetric to the order of the parameters x and y.
	 * @param x the source string
	 * @param y the target
	 * @return the string unit-cost edit distance
	 */
	public static int editDistance(String x, String y) {
		if (x.length() == 0)
			return y.length();
		if (y.length() == 0)
			return x.length();
		String _x, _y;
		if (x.charAt(0) == y.charAt(0)) {
			_x = x.substring(1, x.length());
			_y = y.substring(1, y.length());
			System.out.println(_x);
			return editDistance(_x, _y);
		} else {
			int rmxfst;
			int addxfst;
			int modxfst;

			// add the first label of y to the head of x
			_y = y.substring(1, y.length());
			rmxfst = editDistance(x, _y) + 1;		

			// remove the first lable of x
			_x = x.substring(1, x.length());
			addxfst = editDistance(_x, y) + 1;
			
			// change the fist label of x to the first label of y
			_x = x.substring(1, x.length());
			_y = y.substring(1, y.length());
			modxfst=editDistance(_x, _y)+1;
			
			// return the minimal cost
			int min = rmxfst>addxfst?addxfst:rmxfst;
			min=min>modxfst?modxfst:min;
			return min;


		}

	}

	private static int elementoryEditCost(char a, char b) {
		if (a == b)
			return 0;
		else
			return 1;
	}

}
